package day50_62;

import java.util.Arrays;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author clockTown
 * @Date 2021/6/28 19:05
 * @Version 1.0
 */
public class Solution {
    public int uniquePaths(int m, int n) {
        //判断特例
        if (m == 1 || n == 1){
            return 1;
        }

        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //如果为第一行或第一列，则dp值为1，因为此时不管怎么走都只有一条路线
                if (i == 0 || j == 0){
                    dp[i][j] = 1;
                }else {
                    //如果是其他行列，则值为dp[i- 1][j] 和 dp[i][j - 1]的和
                    dp[i][j] = dp[i- 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n -1];
    }
}
